/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓CS206␈↓ ¬_FINAL EXAMINATION␈↓ 
SPRING 1977 

␈↓ ↓H␈↓␈↓ α_This␈α
examination␈α
is␈α
open␈α
book␈α
and␈α∞notes.␈α
 Write␈α
LISP␈α
functions␈α
as␈α
follows␈α∞except␈α
where
␈↓ ↓H␈↓something else is requested.  Either notation may be used.

␈↓ ↓H␈↓1.␈α
␈↓↓alt1␈α
u␈↓␈αcontains␈α
alternate␈α
elements␈αof␈α
the␈α
list␈α
␈↓↓u␈↓␈αin␈α
the␈α
same␈αorder␈α
as␈α
in␈α␈↓↓u␈↓␈α
ending␈α
with␈α
the␈αlast
␈↓ ↓H␈↓element of ␈↓↓u␈↓.  Thus

␈↓ ↓H␈↓␈↓ α_␈↓↓alt1␈↓ (A B) = (B),

␈↓ ↓H␈↓␈↓ α_␈↓↓alt1␈↓ (A B C) = (A C),

␈↓ ↓H␈↓and

␈↓ ↓H␈↓␈↓ α_␈↓↓alt1␈↓ (A B C D) = (B D).

␈↓ ↓H␈↓2. ␈↓↓iscompact x␈↓, where ␈↓↓x␈↓ is a list structure, is true if all EQUAL subexpressions in ␈↓↓x␈↓ are EQ.

␈↓ ↓H␈↓3.␈α∂␈↓↓partitions␈α∂n␈↓␈α∂is␈α∂a␈α∂list␈α∂of␈α∂the␈α⊂partitions␈α∂of␈α∂the␈α∂integer␈α∂␈↓↓n␈↓␈α∂into␈α∂sums␈α∂of␈α∂smaller␈α⊂integers.␈α∂ Thus
␈↓ ↓H␈↓␈↓↓partitions 1 = ((1)),␈α∞partitions 2 = ((2) (1 1)),␈α∞partitions␈α∞3␈α∞=␈α∞((3) (2 1) (1 1 1)),␈α∂and␈α∞partitions 4 =
␈↓ ↓H␈↓↓((4) (3 1) (2 2) (2 1 1) (1 1 1 1))␈↓.

␈↓ ↓H␈↓4. Define

␈↓ ↓H␈↓␈↓ α_␈↓↓length u ← ␈↓αif␈↓↓ ␈↓αn␈↓↓ u ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 1 + length ␈↓αd␈↓↓ u␈↓,

␈↓ ↓H␈↓and as usual

␈↓ ↓H␈↓␈↓ α_␈↓↓u*v ← ␈↓αif␈↓↓ ␈↓αn␈↓↓ u ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ ␈↓αa␈↓↓ u . [␈↓αd␈↓↓ u * v]␈↓.

␈↓ ↓H␈↓Prove that

␈↓ ↓H␈↓␈↓ α_␈↓↓∀u v.(length[u*v] = length u + length v)␈↓.

␈↓ ↓H␈↓In␈αthe␈αproof␈αyou␈αmay␈αuse␈αany␈αfacts␈α
you␈αlike␈αabout␈αthe␈αproperties␈αof␈αaddition,␈αbut␈αyou␈α
must␈αstate
␈↓ ↓H␈↓what facts you are using.

␈↓ ↓H␈↓5.␈α∂Let␈α⊂␈↓↓e␈↓␈α∂be␈α∂a␈α⊂LISP␈α∂expression␈α⊂formed␈α∂from␈α∂numbers␈α⊂and␈α∂atoms␈α∂using␈α⊂PLUS␈α∂and␈α⊂TIMES␈α∂to
␈↓ ↓H␈↓represent␈α∪addition␈α∪and␈α∩multiplication.␈α∪ ␈↓↓polyprint e␈↓␈α∪is␈α∩a␈α∪list␈α∪of␈α∩the␈α∪characters␈α∪occurring␈α∪in␈α∩a
␈↓ ↓H␈↓printout of ␈↓↓e␈↓ in algebraic notation containing no unnecessary parentheses.  Thus

␈↓ ↓H␈↓␈↓ α_␈↓↓polyprint␈↓␈α∂(TIMES␈α∂(PLUS␈α∂X␈α∂(TIMES␈α∂U␈α∂V␈α∂W))␈α∂X␈α∂Z)␈α∂=␈α∂(LP␈α∂X␈α∂PLUS␈α∂X␈α∂U␈α∂TIMES␈α∞V
␈↓ ↓H␈↓TIMES W RP X Z

␈↓ ↓H␈↓6. What code will LCOM4 generate from (FF (X) (COND ((ATOM X) X) (T (FF (CAR X)))))?